package com.cty.fifteenthDay;

import java.util.ArrayList;
import java.util.List;

/*
 * 给你一个 m 行 n 列的矩阵 matrix ，
 * 请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 * */
public class Q_19 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        List<Integer> integers = spiralOrder(matrix);
        for (int num : integers) {
            System.out.println(num);
        }
    }

    // 力扣官方题解 方法一:模拟
    /*
     * 思路:
     *   定义一个标记数组 在定义顺时针的四个方向 记录元素的总个数
     *   按顺时针的方向遍历 但到达数组的边缘 或者下一个元素被访问过时 换下一个方向
     *   按题意得 数组中的每个元素都会被遍历一边 遍历的条件只要小于（从零开始遍历）元素的总数即可
     * 时间复杂度O(Mn) 空间复杂度O(Mn)
     * */
    public static List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;
        // 定义数组的长和宽
        int row = matrix.length, col = matrix[0].length;
        // 定义一个标记数组
        boolean[][] isVisited = new boolean[row][col];
        // 定义四个方向的坐标改变量
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 记录元素总数
        int total = row * col;
        // 定义当前的横坐标和纵坐标 当前的方向 0表示向右 1表示向下 2表示向左 3表示向上
        int currentRow = 0, currentCol = 0, direction = 0;
        for (int i = 0; i < total; i++) {
            ans.add(matrix[currentRow][currentCol]);
            isVisited[currentRow][currentCol] = true;
            // 计算一下下一个位置的坐标
            int nextRow = currentRow + directions[direction][0];
            int nextCol = currentCol + directions[direction][1];
            //判断下一个位置的坐标是否不符合条件
            if (nextRow < 0 || nextRow >= row || nextCol < 0 || nextCol >= col || isVisited[nextRow][nextCol]) {
                // 如果不符合条件 改变方向
                direction = (direction + 1) % 4;
            }
            //经过判断之后 移动
            currentRow += directions[direction][0];
            currentCol += directions[direction][1];
        }
        return ans;
    }


    // 力扣官方题解 方法二:按层模拟
    /*
     * 将数组看成一层一层的从外到内模拟
     *
     * 时间复杂度O(Mn) 空间复杂度O(1)
     *
     * */
    public static List<Integer> spiralOrder2(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;
        int row = matrix.length, col = matrix[0].length;
        // 定义本圈模拟的上下左右边界
        int left = 0, right = col - 1, top = 0, bottom = row - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                // 加入上边界的值
                ans.add(matrix[top][i]);
            }
            for (int i = top + 1; i <= bottom; i++) {
                //加入右边界的值
                ans.add(matrix[i][right]);
            }
            // 判断边界是否重合
            if (left < right && top < bottom) { //不重合
                // 加入下边界
                for (int i = right - 1; i > left; i--) {
                    ans.add(matrix[bottom][i]);
                }
                // 加入左边界
                for (int i = bottom; i > top; i--) {
                    ans.add(matrix[i][left]);
                }
            }
            // 缩小圈
            left++;
            right--;
            top++;
            bottom--;
        }
        return ans;
    }
}
